package real.unknown.dynamic;

// import jdk.javadoc.internal.doclets.formats.html.resources.standard;

public class ShortestPath {
    /* 
        输入描述:
            第一行表示矩阵大小 n，5 <n < 10000
            第二行表示起点和终点的坐标
            第三行起是一个用矩阵表示的游戏地图，其中#或者@表示障碍物，
            其他字母、非0数字、以及符号+、-、* 等等均表示普通可达格子，共有 n 行  n 列 

        输出描述:
            输出最优路径的长度；若无法到达，则输出-1

        输入例子1:
            15
            0 7 7 7
            *5#++B+B+++++$3
            55#+++++++###$$
            ###$++++++#+*#+
            ++$@$+++$$$3+#+
            +++$$+++$+4###+
            A++++###$@+$++A
            +++++#++$#$$+++
            A++++#+5+#+++++
            +++$$#$++#++++A
            +++$+@$###+++++
            +###4+$+++$$+++
            +#+3$$$+++$##++
            +#*+#++++++#$$+
            $####+++++++$##
            3$+++B++B++++#5

        输出例子1:
            13
    */

    static class Main {
        char[][] p;
        public int shortestPath(char[][] p) {
            int m, n;
            if (p == null || (m = p.length) == 0 || (n = p[0].length) == 0) return -1;
            this.p = p;
            int[][] f = new int[m][n];
            for (int i = 0; i < m; i++) {
                f[i][0] = 0; 
            }
            return f[m - 1][n - 1];
        }

        public boolean isPath(int i, int j) {
            char c = p[i][j];
            return c != '#' && c != '@';
        }
    }
}
